package 分治.快排;

import java.util.Random;
//参考颜色划分，在杂乱的数组中随机选一个数，将数组分三块， 小于，等于，大于
// 然后将小于，和大于重新进行排序，直到全部为增序为止
public class 排序数组912 {

    //快速排序
    public  int [] sortArray(int [] nums){
        qsort(nums,0,nums.length-1);
        return nums;
    }
    public void qsort(int [] nums,int l,int r){
        if(l>=r) return ;

        // 数组分三块
        int key = nums[new Random().nextInt(r-l+1)+l];
        int right = r+1,left = l-1,i = l;
        while(i<right)
        {
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]>key) swap(nums,--right,i);
            else i++;
        }
        // [l,left]  [left+1,right-1] [ right,r]
        qsort(nums,l,left);
        qsort(nums,right,r);

    }
    public void swap(int [] nums,int i,int j)
    {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }




}

